#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <cassert>

int *preKmp(const char *x) {
		int i, j;
		int m = strlen(x);
		int *next = new int[m];

		next[0] = -1; // -1 : initial state(0 first character, so -1 before 0, stand for initial state) 
		i = 0;  // first character's index
		j = -1; // initial state


		/* compute the character i+1 state from state i */
		while (i < m) { 
				// j: last successful match substring index
				// i: last compute character's index */
				while (j > -1 && x[i] != x[j])
						j = next[j];
				// no match or found one match
				// i, j go ahead
				++i;
				++j;

				if (x[i] == x[j]) 
					// if t[k] and x[i] are not match, we know that t[k] and x[j] will be not match again.
					// because x[i] == x[j]
					// so we just skip i, set next[i] skip j;
						next[i] = next[j];
				else
					// in this state, if t[k] and x[j] are not match, because x[i]!=x[j],
					// so we can not judge that t[k] and x[j] will not match too.
					// so j may be another match index. 
					// so we set next[i] to j
						next[i] = j;
		}
}

void print_next(const char *pattern, int *next) {
	for (int i=0;i<strlen(pattern);i++) {
		std::cout<<std::setw(10)<<std::left;
		std::cout<<i;
	}
	std::cout<<std::endl;

	for (int i=0;i<strlen(pattern);i++) {
		std::cout<<std::setw(10)<<std::left;
		std::cout<<*(pattern+i);
	}
	std::cout<<std::endl;

	for (int i=0;i<strlen(pattern);i++) {
		std::cout<<std::setw(10)<<std::left;
		std::cout<<*(next+i);
	}
	std::cout<<std::endl;
}


void KMP(const char *x, int m, const char *y, int n) {
   int i, j;
   int *next = preKmp(y);

   i = j = 0;
   while (j < n) {
      while (i > -1 && x[i] != y[j]) // found a match
         i = *(next+i);
      i++;
      j++;
      if (i >= m) {
         printf("%s\n",x+j-i);
         i = *(next+i);
      }
   }
}


int main() {
	const char * pattern = "name";
	int *next=preKmp(pattern);
	print_next(pattern,next);
	
	const char *text = "hello,my name is junix.";
	KMP(text, strlen(text), pattern, strlen(pattern));
}

